﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using UFPE.CIn.Abc.Primality.Util;
using System.Diagnostics;

namespace UFPE.CIn.Abc.Primality.Algorithms
{
    public class FermatPrimalityTest : BaseConfidenceAlgorithm
    {
        public override string AlgorithmName
        {
            get
            {
                return "Pequeno teorema de Fermat";
            }
        }

        private static FermatPrimalityTest instance;

        public static FermatPrimalityTest Instance
        {
            get
            {
                if (instance == null)
                {
                    instance = new FermatPrimalityTest();
                }

                return instance;
            }
        }

        public override bool IsPrime(BigInteger val)
        {
            return IsPrime(val, 20, false);
        }

        public override bool IsPrime(BigInteger val, bool pass)
        {
            return IsPrime(val, 20, pass);
        }

        //***********************************************************************
        // Probabilistic prime test based on Fermat's little theorem
        //
        // for any a < p (p does not divide a) if
        //      a^(p-1) mod p != 1 then p is not prime.
        //
        // Otherwise, p is probably prime (pseudoprime to the chosen base).
        //
        // Returns
        // -------
        // True if "this" is a pseudoprime to randomly chosen
        // bases.  The number of chosen bases is given by the "confidence"
        // parameter.
        //
        // False if "this" is definitely NOT prime.
        //
        // Note - this method is fast but fails for Carmichael numbers except
        // when the randomly chosen base is a factor of the number.
        //
        //***********************************************************************

        public override bool Helper(BigInteger thisVal, int confidence)
        {
            int bits = thisVal.bitCount();
            BigInteger a = new BigInteger();
            BigInteger p_sub1 = thisVal - (new BigInteger(1));
            Random rand = new Random();

            for (int round = 0; round < confidence; round++)
            {
                bool done = false;

                while (!done)		// generate a < n
                {
                    int testBits = 0;

                    // make sure "a" has at least 2 bits
                    while (testBits < 2)
                        testBits = (int)(rand.NextDouble() * bits);

                    // Generating only coprimes to comply with Fermat's Little Theorem.
                    // While using the original implementation is more accurate and less prone to Carmichael numbers
                    // this implementation is able to show the generation of Carmichael pseudoprimes
                    a = thisVal.genCoPrime(testBits, rand);

                    int byteLen = a.dataLength;

                    // make sure "a" is not 0
                    if (byteLen > 1 || (byteLen == 1 && a.IsZerothBitDiffOfOne()))
                        done = true;
                }

                // check whether a factor exists (fix for version 1.03)
                //BigInteger gcdTest = a.gcd(thisVal);
                //if (gcdTest.dataLength == 1 && gcdTest.IsZerothBitDiffOfOne())
                //    return false;

                // calculate a^(p-1) mod p
                BigInteger expResult = a.modPow(p_sub1, thisVal);

                int resultLen = expResult.dataLength;

                // is NOT prime is a^(p-1) mod p != 1

                if (resultLen > 1 || (resultLen == 1 && expResult.IsZerothBitDiffOfOne()))
                {
                    //Console.WriteLine("a = " + a.ToString());
                    return false;
                }
            }

            return true;

        }
    }
}
